/**
 * 判断字符串是否是中心对称的
 * 
 * 
 * 思想：用一个stack保存字符串的一半，向下取整即可
 * 偶数个[1,2,3,4]  4/2=2 要-1  ，而右半边的开头是4/2
 * 奇数个[1,2,1]  3/2=1 要-1  ，右边的开头是1+1=2  ,所以这个要+1
 * 
 */

#include"stack.h"
/**
 * 这里没有linkedList结构体，就用array代替了
 * 
 * 注意，在linkedList情况下，有更优的解法
 * 就是快慢指针找中间结点，后半部分反转
 * 从头和中间位置用两个指针同时往后走，判断是否相同
 * 此时时间复杂度和空间复杂度分别为n和1
 * 
 * 若用stack，则空间复杂度为n
 */
int solution(char arr[],int n){
    SqStack s;//初始化辅助栈
    initStack(&s);
    int temp=n/2-1;
    //确实是要用两个循环的
    for(int i=0;i<=temp;i++){
        pushStack(&s,arr[i]);
    }
    int begin= n%2==0? n/2 : n/2+1;
    for(int i=begin;i<n;i++){
        int tempX=0;
        popStack(&s,&tempX);
        if(tempX==arr[i]){
            continue;
        }
        return 0;//如果不等于，就返回false
    }
    if(stackEmpty(&s)){//最后如果栈空了，才能确定是对称的
        return 1;
    }else{
        return 0;
    }
}